package algo.A03_递归和算法复杂度;

import util.ArrayUtil;

import java.util.Arrays;

/**
 * 二分查找递归解法
 * 找重复：每次要取一半的元素继续查找
 * 找变化：变化的量应该作为参数
 * 找出口：低位坐标大于高位时退出
 */
public class T09_二分查找 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 1, 100);
        arr[0] = 50;
        Arrays.sort(arr);
        ArrayUtil.print(arr);
        int result = solution(arr,0,arr.length - 1,50);
        System.out.println("result = " + result);
    }

    /**
     * 二分查找递归方法
     *
     * @param arr  被查找的数组
     * @param low  低位
     * @param high 高位
     * @param key  要查找的元素
     * @return
     */
    private static int solution(int[] arr, int low, int high, int key) {
        if (low > high) {
            return -1;
        }
        //找中点
        int mid = low + (high - low) / 2;
        //key比中间值大，low要调整为中点右边
        if (key > arr[mid]) {
            return solution(arr, mid + 1, high, key);
        //key比中间值小，high要调整为中点左边
        } else if (key < arr[mid]){
            return solution(arr,low,mid - 1,key);
        //key==中间值时说明找到了，返回下标
        }else {
            return mid;
        }
    }
}
